import org.w3c.dom.ls.LSException;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}
class Solution1 {
    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;


        boolean tmp1 = isValidBST(root.left);
        if(!tmp1) return false;

        if(prev >= root.val) return false;
        prev = root.val;

        boolean tmp2 = isValidBST(root.right);
        if(!tmp2) return  false;

        return true;
    }
}

class Solution2 {
    int ret;
    int count = 0;
    public int kthSmallest(TreeNode root, int k) {
        if(root.left!=null) {
            kthSmallest(root.left,k);
            if(count == k) return ret;
        }

        count++;
        ret = root.val;
        if(count == k) return ret;

        if(root.right!=null) {
            kthSmallest(root.right,k);
            if(count == k) return ret;
        }
        return ret;
    }
}


class Solution3 {
    StringBuffer str = new StringBuffer();
    List<String> list = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        if(root.left == null && root.right == null) {
            StringBuffer tmp = new StringBuffer(root.val+"");
            int len = tmp.length();
            str.append(tmp);
            list.add(str.toString());
            str.delete(str.length()-len, str.length());
        }else {
            StringBuffer tmp = new StringBuffer(root.val+"->");
            System.out.println(tmp);
            int len = tmp.length();
            str.append(tmp);
            System.out.println("str:"+str);

            if(root.left!=null) {
                binaryTreePaths(root.left);
            }
            if(root.right!=null) {
                binaryTreePaths(root.right);
            }
            str.delete(str.length()-len, str.length());
        }
        return list;
    }
}


class Solution4 {
    List<List<Integer>> lists = new ArrayList<>();
    int[] arr;
    boolean[] st;
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        st = new boolean[n];
        arr = new int[n];
        dfs(nums,0);
        return lists;
    }
    public void dfs(int[] nums,int n) {
        if(n == nums.length) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i<nums.length; i++) {
            if(!st[i]) {
                list.add(nums[i]);
                st[i] = true;
                dfs(nums,n+1);
                st[i] = false;
                list.remove(list.size()-1);
            }
        }
    }
}

class Solution5 {
    List<List<Integer>> lists = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        dfs(nums,0);
        return lists;
    }
    public void dfs(int[]nums, int n) {
        if(n == nums.length) {
            lists.add(new ArrayList<>(list));
        }
        for(int i = 0; i<nums.length; i++){
            //选
            list.add(nums[i]);
            dfs(nums,n+1);
            //不选
            dfs(nums,n+1);

            list.remove(list.size()-1);
        }
    }
}

class Solution {
    List<List<Integer>> lists = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        dfs(nums,0);
        return lists;
    }
    public void dfs(int[]nums, int i) {
        if(i == nums.length) {
            lists.add(new ArrayList<>(list));
            return;
        }
        //不选
        dfs(nums,i+1);
        //选
        list.add(nums[i]);
        dfs(nums,i+1);
        list.remove(list.size()-1);
    }
}












